package com.dataStructure.Map;

import java.util.*;

/**
 * 哈希法是比较巧妙的，一定要善于观察可以用哈希的地方，我们做哈希方法一般思路就是，
 */
public class LeetCode {

    public static void main(String[] args) {

    }



    /**
     * 三数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        ArrayList<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length;) {
            int e = nums[i];
            List<List<Integer>> lists = twoSum2(nums, i + 1, -e);
            for (List<Integer> list : lists) {
                    list.add(e);
                    result.add(list);
            }
            i++;
            while(i < nums.length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }

        }

        return result;
    }

    public List<List<Integer>> twoSum2(int[] nums,int start, int target) {
        ArrayList<List<Integer>> result = new ArrayList<>();

        int left = start; int right = nums.length - 1;
        while (left < right) {

            int leftV = nums[left]; int rightV = nums[right];
            int sum = nums[left] + nums[right];
            if (sum == target) {
                System.out.println(left + "  " + right + " " + target);
                System.out.println("sdf");

                ArrayList<Integer> list = new ArrayList<>();
                list.add(nums[left]);
                list.add(nums[right]);
                result.add(list);
                while(leftV == nums[left] && left < right) {
                    left++;
                }
                while(rightV == nums[right] && left < right) {
                    right--;
                }
            }
            else if (sum < target) {
                left++;
            }
            else  {
                right--;
            }
        }

        return result;
    }

    /**
     * 两数之和：双指针法
     */
    public int[] twoSum(int[] nums, int target) {
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length - 1;
        //不能用等于
        while (left < right) {
            int sum = nums[right] + nums[left];
            if (sum == target) {
                return new int[]{left, right};
            }
            else if (sum < target) {
                left ++;
            }
            else {
                right -- ;
            }
        }
        return null;
    }

    /**
     * 350. 两个数组的交集 II
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map1 = new HashMap<>();
        HashMap<Integer, Integer> map2 = new HashMap<>();
        for (int e : nums1) {
            map1.putIfAbsent(e, 0);
            map1.put(e, map1.get(e) + 1);
        }

        for (int e : nums2) {
            map2.putIfAbsent(e, 0);
            map2.put(e, map2.get(e) + 1);
        }
        ArrayList<Integer> list = new ArrayList<>();

        for (Map.Entry<Integer, Integer> e : map1.entrySet()) {
            Integer val2 = map2.get(e.getKey());
            if (val2 != null) {
                int min = Integer.min(e.getValue(), val2);
                for (int i = 0; i < min; i++) {
                    list.add(e.getKey());
                }
            }
        }
        return list.stream().filter(integer -> integer!=null).mapToInt(i->i).toArray();
    }

    /**
     * 438. 找到字符串中所有字母异位词
     */
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> list = new ArrayList<>();
        int l = p.length();
        char[] chars = p.toCharArray();
        Arrays.sort(chars);
        String s1 = new String(chars);

        int i = 0; int j = i + l - 1;
        while (j < s.length()) {
            String substring = s.substring(0, j + 1);
            char[] subChar = substring.toCharArray();
            Arrays.sort(subChar);
            if (s1.equals(new String(subChar))) {
                list.add(i);
            }
            i++;
            j++;
        }

        return list;
    }
    /**
     * 多数元素
     * 力扣 169
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.putIfAbsent(num, 0);
            if ((map.get(num) + 1) > nums.length /2)
                return num;
            map.put(num, map.get(num) + 1);

        }
        return 1;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();
        for (String e : strs) {
            char[] ar = e.toCharArray();
            Arrays.sort(ar);
            String s = new String(ar);
            if (map.get(s) == null) {
                ArrayList<String> list = new ArrayList<>();
                list.add(e);
                map.put(s, list);
            } else {
                map.get(s).add(e);
            }
        }
        List<List<String>> result = new ArrayList<>();
        for (List<String> list : map.values()) {
            result.add(list);
        }


        return result;
    }


    /**
     * 长按键入
     * @param name
     * @param typed
     * @return
     */
    public boolean isLongPressedName(String name, String typed) {
        HashSet<Character> namch = new HashSet<>();
        HashSet<Character> typedh = new HashSet<>();

        char[] namec = name.toCharArray();
        char[] typedc = typed.toCharArray();
        for (int i = 0; i < typedc.length; i++) {
            char c = typedc[i];
            typedh.add(c);
        }
        for (char c : namec) {
            namch.add(c);
        }
        if (!namch.equals(typedh)) {
            return false;
        }
        if (namec[0] != typedc[0]) {
            return false;
        }

        for (int i = 1 ,j = 1; j < typedc.length || i < name.length() ;) {
            System.out.println(i);
            if (namec[i] != typedc[j]) {
                if (typedc[j] == namec[i - 1]) {
                    j++;
                    //将map2的value 加一
//                    if (map2.get(typedc[j]) == null) {
//                        map2.put(typedc[j],0);
//                    } else {
//                        map2.put(typedc[j],)
//                    }
                } else {
                    return false;
                }
            }
            else {
                if (i >= name.length() -1) {
                    j++;
                } else {
                    j++;
                    i++;
                }

            }
        }

        return true;
    }

    /**
     * //力扣 同构字符串
     * bbbaaaba   aaabbbba
     * @param s
     * @param t
     * @return
     */
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Character> maps = new HashMap<>();
        HashMap<Character, Character> mapt = new HashMap<>();
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        for (int i = 0; i < s1.length; i++) {
            if (!maps.containsKey(s1[i]) && !mapt.containsKey(t1[i])) {
                maps.put(s1[i],t1[i]);
                mapt.put(t1[i],s1[i]);
            }
            else if (maps.containsKey(s1[i]) && mapt.containsKey(t1[i])) {
                if (!maps.get(s1[i]).equals(t1[i])  || !mapt.get(t1[i]).equals(s1[i])) {
                    return false;
                }
                continue;
            }
            else {
                return false;
            }
        }
        return true;
    }


    /**
     * 力扣 454
     * @param nums1
     * @param nums2
     * @param nums3
     * @param nums4
     * @return
     */
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer,Integer> map1 = new HashMap<Integer,Integer>();

        for (int i = 0 ;i < nums1.length; i++) {
            for (int j =0 ;j < nums2.length ; j++) {
                if (map1.containsKey(nums1[i] + nums2[j])) {
                    map1.put(nums1[i] + nums2[j], map1.get(nums1[i] + nums2[j]) + 1);
                } else {
                    map1.put(nums1[i] + nums2[j],1);
                }
            }
        }
//        HashMap<Integer,Integer> map2 = new HashMap<>();
        int ct = 0;
        for (int i = 0 ;i < nums3.length; i++) {
            for (int j =0 ;j < nums4.length ; j++) {
                if (map1.containsKey(0 - nums3[i] - nums4[j])) {
                   ct+= map1.get(0-nums3[i] - nums4[j]);
                }
            }
        }

        return ct;


    }

    /**
     * 力扣 349 两个数组的交集
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        HashSet<Integer> integers = new HashSet<>();
        

        return null;
    }

    /**
     * 力扣  209 ， 用数组去模拟哈希 利用字符的ASCII码值 分别落地到26个卡槽中 ，然后根据
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram2(String s, String t) {
        int[] ar = new int[26];

        for (char e : s.toCharArray()) {
            ar[e - 'a']++;
        }

        for (char e : t.toCharArray()) {
            ar[e - 'a']--;
        }

        for (int e : ar) {
            if (e != 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 力扣 242 有效字母的异位词  此法不够巧妙，用 HashMap 去计数，最后比较还使用equals() 未免太牵强了
     * @param s
     * @param t
     * @return
     */
    public boolean isAnagram(String s, String t) {
        HashMap<Character,Integer> map = new HashMap<>();
        HashMap<Character,Integer> map2 = new HashMap<>();
        for (char e : s.toCharArray()) {
            if (map.get(e) == null) {
                map.put(e,1);
            } else {
                map.put(e,map.get(e) + 1);
            }
        }

        for (char e : t.toCharArray()) {
            if (map2.get(e) == null) {
                map2.put(e,1);
            } else {
                map2.put(e,map2.get(e) + 1);
            }
        }
        return map.equals(map2);

    }




}
